package problems.daily;

/**
 * 1234. 替换子串得到平衡字符串
 * <p>https://leetcode.cn/problems/replace-the-substring-for-balanced-string/</p>
 *
 * @author habitplus
 * @since 2023/2/13 15:28
 */
public class DT1234 {
    public int balancedString(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] cntMap = new int[26];
        int avg = n / 4;

        // 建立计数表
        for (char c : chs) {
            ++cntMap[c - 'A'];
        }

        if (check(cntMap, avg)) {
            return 0;
        }

        int r = 0;
        int ans = n;
        for (int l = 0; l < n; ++l) {
            while (r < n && !check(cntMap, avg)) {
                --cntMap[chs[r] - 'A'];
                ++r;
            }

            if (!check(cntMap, avg)) break;
            ans = Math.min(ans, r - l);
            ++cntMap[chs[l] - 'A'];
        }

        return ans;
    }

    private boolean check(int[] map, int avg) {
        return map['Q' - 'A'] <= avg
                && map['W' - 'A'] <= avg
                && map['E' - 'A'] <= avg
                && map['R' - 'A'] <= avg;
    }
}
